package com.gxc.recursion;

/**
 * 假设s和m初始化，s ="a";m = s;
 * 再定义两种操作，
 * 第一种操作:
 * m = s;
 * s=s+s;
 * 第二种操作
 * s=s+m;
 * 求最小的操作步骤数，可以将s拼接到长度等于n
 *
 * 解法：
 * 1：由步骤2 可得，最多 执行 n-1 个步骤2 ，s可拼接到长度等于n，所以执行步骤大于 n-1 都不符合最小条件
 */
public class Minimum {

    public static void main(String[] args) {

    }

    /**
     *
     * @param targetLength  目标长度 n
     * @param s
     * @param m
     * @param cur   当前次数
     * @param max   最大次数
     * @return
     */
    public static int splice(int targetLength, String s, String m, int cur, int max) {
        //如果递归的次数已经大于可找到的条件次数，则返回一个很大的步骤数
        if (cur>max) return Integer.MAX_VALUE;
        //如果s的长度大于目标n长度，则返回一个很大的步骤数
        if (s.length() > targetLength) return Integer.MAX_VALUE;
        //如果s的长度等于目标n长度，则返回当前步骤数
        if (s.length() == targetLength) return cur;

        String tempS = s;
        String tempM = m;
        //第一种操作
        int stepsOne = splice(targetLength, tempS + tempS, tempS, cur + 1, max);
        //第二种操作
        int stepsTwo = splice(targetLength, tempS + tempM, tempM, cur + 1, max);
        return Math.min(stepsOne, stepsTwo);
    }

    /**
     * 当n为质数时，不能在第一步之外调用操作一(当n为2时调用一次操作一或二就结束了，不存在第二步，所以不讨论n为2的情况)，
     * 因为一旦在第一步之外调用操作一，假设调用之前s=x个a(x≠1)，调用操作一后s=2x个a，m=x个a，
     * 那么当前得到的s与m就会拥有x这个相同的因子，以后不管怎么调用都拼不成质数了，调用步骤一就会导致s有2这个因子，调用步骤二会导致s有x这个因子。而第一步调用操作一也不会让总步骤数变少，所以得出结论，当n为质数时只能调用步骤二，最少的步骤数就是n-1。
     * 当n不是质数时，那么它就是合数(1既不是质数也不是合数，但是s开始就有1个a，步骤数是0，所以忽略1)，
     * 任何合数都可以被分解为质数相乘的形式，
     * 假设n = X*Y*Z(X、Y、Z都是质数)，
     * s变为X需要X-1步，
     * 把X看作是开始的默认a，怎么把它变成Y，
     * 同样需要Y-1步，同理变成Z需要Z-1步，所以总体需要X+Y+Y-3步，
     * 即把合数分解质因数后，最少步骤数就是质数因子的和再减去质数因子的个数
     * @return
     */
    public static int splice2(int n) {
        if (n < 1) return 0;

        if (isPrime(n)) {
            return n-1;
        }
        //合数分解成质数相乘
        int[] decomposition = compositeDecomposition(n);
        return decomposition[0] - decomposition[1];
    }

    private static int[] compositeDecomposition(int n) {
        //质数的和
        int sum = 0;
        //质数的个数
        int count = 0;
        for (int i = 2; i <= n ; i++) {
            while (n%i == 0) {
                //质数的和
                sum += i;
                //质数的个数
                count++;
                //n除以i
                n/=i;
            }
        }
        int[] array = new int[2];
        array[0] = sum;
        array[1] = count;
        return array;
    }

    /**
     * 判断是否质数
     * @param n
     * @return
     */
    private static boolean isPrime(int n) {
        for (int i = 2; i < n; i++) {
            if (n%i == 0) return false;
        }
        return true;
    }

}
